# utf-8
from collections import deque

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}


def my_bfs(graph, start):
    # FIXME: cannot work
    visited = set()
    queue = list()

    queue.insert(0, start)
    visited.add(start)

    level = 0
    while len(queue) != 0:
        level = level + 1
        cur_len = len(queue)
        for i in range(cur_len):
            node = queue.pop()
            print(f"[{level}]node: {node}")
            for neighbor in graph[node]:
                if neighbor not in visited:
                    # print(f"[{level}]negihbor: {neighbor}")
                    queue.insert(0, neighbor)
                    visited.add(neighbor)
    pass


def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)


bfs(graph, "A")
my_bfs(graph, "A")
